package com.二叉搜索树.练习题;

public class Leetcode1008 {
    /**
     * 前序遍历构造二叉搜索树
     * 给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
     * 保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
     * 二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。
     * 二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
     * 输入：preorder = [8,5,1,7,10,12]
     * 输出：[8,5,10,1,7,null,12]
     */
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            insertIntoBST(root, preorder[i]);
        }
        return root;
    }

    private TreeNode insertIntoBST(TreeNode node, int val) {
        if(node == null){
            return new TreeNode(val);
        }
        if(val < node.val){
            node.left = insertIntoBST(node.left, val);
        }
        if(val > node.val){
            node.right = insertIntoBST(node.right, val);
        }
        return node;
    }
}
